package algorithm.middle;

import java.util.ArrayList;
import java.util.List;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-03-15 20:27
 * @Description:给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * 54. 螺旋矩阵
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/spiral-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SpiralOrder54 {
    //从外围顺着边往里走
    int INF = 101;

    public List<Integer> spiralOrder(int[][] mat) {
        List<Integer> ans = new ArrayList<>();
        int m = mat.length, n = mat[0].length;
        // 定义四个方向
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int x = 0, y = 0, d = 0, i = 0; i < m * n; i++) {
            ans.add(mat[x][y]);
            mat[x][y] = INF;

            // 下一步要到达的位置
            int nx = x + dirs[d][0], ny = y + dirs[d][1];
            // 如果下一步发生「溢出」或者已经访问过（说明四个方向已经走过一次）
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || mat[nx][ny] == INF) {
                d = (d + 1) % 4;
                nx = x + dirs[d][0];
                ny = y + dirs[d][1];
            }

            x = nx;
            y = ny;
        }
        return ans;
    }


    /**
     * 59. 螺旋矩阵 II
     * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
     * <p>
     * 示例 1：
     * <p>
     * 输入：n = 3
     * 输出：[[1,2,3],[8,9,4],[7,6,5]]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/spiral-matrix-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int[][] generateMatrix(int n) {
        int size = n * n;
        //结果数组
        int[][] arr = new int[n][n];
        //方向 右，下，左，上
        int[][] way = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 1, x = 0, y = 0, d = 0; i <= size; i++) {
            arr[x][y] = i;
            //下一步要到达的位置
            int nx = x + way[d][0];
            int ny = y + way[d][1];

            //位置溢出或者已经走过
            if (nx >= n || ny >= n || nx < 0 || ny < 0 || arr[nx][ny] != 0) {
                d = (d + 1) % 4;
                nx = x + way[d][0];
                ny = y + way[d][1];
            }
            x = nx;
            y = ny;
        }
        return arr;
    }












    /**
     * @param matrix
     * @return
     */

    public List<Integer> spiralOrder2(int[][] matrix) {
        //行下边界，列上边界，行上边界，列下边界
        int[] boundary = new int[]{0, matrix[0].length, matrix.length, -1};
        //int 方向 0-向上 1-向右 2-向下 3-向左
        int direction = 1;
        int max = matrix.length * matrix[0].length;
        int x = 0, y = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < max; i++) {
            res.add(matrix[x][y]);
            switch (direction) {
                case 1:
                    //右
                    if (y +1 == boundary[1]) {
                        //临界值
                        direction = 2;
                        x++;
                        boundary[1]--;
                    }else {
                        y++;
                    }
                    break;
                case 2:
                    //下
                    if (x + 1 == boundary[2]) {
                        direction = 3;
                        y--;
                        boundary[2]--;
                    }else {
                        x++;
                    }
                    break;
                case 3:
                    if (y - 1 == boundary[3]) {
                        direction = 0;
                        x--;
                        boundary[3]++;
                    }else {
                        y--;
                    }
                    break;
                case 0:
                    if (x - 1 == boundary[0]) {
                        direction = 1;
                        y++;
                        boundary[0]++;
                    }else {
                        x--;
                    }
                    break;
            }
        }
        return res;
    }
}
